<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
// Scaling + push maximum possible flow throw the path
// Test 48 --&gt; 3.13 sec

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;algorithm&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)

#define I64 "%I64d"
typedef long long ll;

#define maxv 503
#define maxe 20010

int e = 2, n, m, he[maxv], ne[maxe], to[maxe], c[maxe], c0[maxe];
int cc, u[maxv];
int pn, pa[maxv];

int dfs( int v, int k )
{                  
  int x;
  u[v] = cc;
  for (int i = he[v]; i; i = ne[i])
    if (c[i] &gt;= k && ((x = to[i]) == n || (u[x] != cc && dfs(x, k))))
    {
      pa[pn++] = i;
      return 1;       
    }
  return 0;
}

ll MaxFlow()
{
  ll res = 0;
  memset(u, 0, sizeof(u)), cc = 1;
  for (int k = 1 &lt;&lt; 30; k &gt; 0; k &gt;&gt;= 1)
  {
    cc++, pn = 0;
    while (dfs(1, k))
    {
      int mi = 2 * k;
      forn(i, pn)
        mi = min(mi, c[pa[i]]);
      res += mi;
      forn(i, pn)
      {
        int e = pa[i];
        c[e] -= mi, c[e ^ 1] += mi;
      }
      cc++, pn = 0;
    }
  }
  return res;
}

int main()
{
  freopen("flow2.in", "r", stdin);
  freopen("flow2.out", "w", stdout);

  scanf("%d%d", &n, &m);
  forn(i, m)
  {
    int a, b, _c;
    scanf("%d%d%d", &a, &b, &_c);
    c0[i] = _c;
    ne[e] = he[a], to[e] = b, c[e] = _c, he[a] = e++;
    ne[e] = he[b], to[e] = a, c[e] = 0, he[b] = e++;
  }

  printf(I64"\n", MaxFlow());
  forn(i, m)
    printf("%d\n", c0[i] - c[2 * i + 2]);
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
